#ifndef ASTAR_H__
#define ASTAR_H__

#include <bits/stdc++.h>
#include "main.h"
using namespace std;

const int next_position[4][2] = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} }; // 定义方向


typedef struct Node
{
    Point p;
    int F; // 总代价值 = G + H
    int G; // 起点到该点的代价
    int H; // 该点到终点的预估代价
    Node* father;
    Node(int _x, int _y) : F(0), G(0), H(0), father(NULL)
    {
        p.x = _x;
        p.y = _y;
    }
    // 重载操作符，使优先队列以F值大小为标准维持小顶堆
    bool operator<(const Node& n) const
    {
        return F == n.F ? G > n.G : F > n.F;
    }
} Node;

// 计算曼哈顿距离
inline int Manhattan(const Point& a, const Point& b) { return (abs(a.x - b.x) + abs(a.y - b.y)); }

// a*算法
void Astar(int x_end, int y_end, int x_start, int y_start, vector<Point> &ans, int type);

void astar_conflict(int x_start, int y_start, int x_end, int y_end, vector<Point> &ans, int type);

#endif
